{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Output Contest Matches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findContestMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #输出比赛匹配对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>在 NBA 季后赛期间，我们总是安排相对强大的球队与相对弱小的球队比赛，就像让排名第 <code>1</code> 的球队与排名第 <code>n</code> 的球队比赛一样，这是一种使比赛更加有趣的好策略。</p>\n",
    "\n",
    "<p>现给定 <code>n</code> 支球队，请以字符串的形式返回它们的最终的比赛匹配方案。</p>\n",
    "\n",
    "<p>这 <code>n</code> 支球队从 <code>1</code> 到 <code>n</code> 进行标记，代表它们的初始排名（即，排名 <code>1</code> 的是最强的球队，排名 <code>n</code> 的是最弱的球队）。</p>\n",
    "\n",
    "<p>我们将使用括号 <code>'('</code> 和 <code>')'</code> 以及逗号 <code>','</code> 来表示比赛的匹配情况。我们使用括号来表示匹配，逗号来表示分组。在每一轮的匹配过程中，你总是需要遵循使相对强大的球队与相对弱小的球队配对的策略。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 4\n",
    "<strong>输出:</strong> \"((1,4),(2,3))\"\n",
    "<strong>解释:</strong> \n",
    "在第一轮，我们将队伍 1 和 4 配对，2 和 3 配对，以满足将强队和弱队搭配的效果。得到(1,4),(2,3).\n",
    "在第二轮，(1,4) 和 (2,3) 的赢家需要进行比赛以确定最终赢家，因此需要再在外面加一层括号。\n",
    "于是最终答案是((1,4),(2,3))。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 8\n",
    "<strong>输出:</strong> \"(((1,8),(4,5)),((2,7),(3,6)))\"\n",
    "<strong>解释:</strong> \n",
    "第一轮: (1,8),(2,7),(3,6),(4,5)\n",
    "第二轮: ((1,8),(4,5)),((2,7),(3,6))\n",
    "第三轮 (((1,8),(4,5)),((2,7),(3,6)))\n",
    "由于第三轮会决出最终胜者，故输出答案为(((1,8),(4,5)),((2,7),(3,6)))。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == 2x</code>，并且 <code>x</code> 在范围 <code>[1,12]</code> 内。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [output-contest-matches](https://leetcode.cn/problems/output-contest-matches/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [output-contest-matches](https://leetcode.cn/problems/output-contest-matches/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        q=[str(i) for i in range(1,n+1)]\n",
    "        while len(q)>1:\n",
    "            next_q=[]\n",
    "            while q:\n",
    "                v=f'({q.pop(0)},{q.pop(-1)})'\n",
    "                next_q.append(v)\n",
    "            q=next_q\n",
    "        return q[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        Q = [str(x) for x in range(1, n + 1)]\n",
    "        while len(Q) > 1:\n",
    "            nxt_Q = []\n",
    "            while Q:\n",
    "                x = Q.pop(0)\n",
    "                y = Q.pop(-1)\n",
    "                nxt_Q.append('(' + x + ',' + y + ')')\n",
    "            Q = nxt_Q\n",
    "        return Q[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "      ans = [0] * n\n",
    "      def dfs(num, gap):\n",
    "        if num == 2:\n",
    "          ans[0::gap] = [\"1\", \"2\"]\n",
    "          return\n",
    "        \n",
    "        dfs(num // 2, gap * 2)\n",
    "        for i in range(gap, n, gap * 2):\n",
    "          ans[i] = str(1 + num - int(ans[i - gap]))\n",
    "      \n",
    "      dfs(n, 1)\n",
    "      while len(ans) > 1:\n",
    "        temp = []\n",
    "        for i in range(0, len(ans), 2):\n",
    "          temp.append(\"(\" + ans[i] + \",\" + ans[i+1] + \")\")\n",
    "        ans = temp\n",
    "      return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        q = [str(i) for i in range(1,n+1)]\n",
    "        while len(q) > 1:\n",
    "            sz =len(q)\n",
    "            new = []\n",
    "            for i in range(sz//2):\n",
    "                new.append('({},{})'.format(q[i], q[sz-1-i]))\n",
    "            if sz % 2 == 1:\n",
    "                new.append('{}'.format(q[sz//2]))\n",
    "            q = copy.deepcopy(new)  \n",
    "        return q[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        Q = [str(x) for x in range(1, n + 1)]\n",
    "        while len(Q) > 1:\n",
    "            nxt_Q = []\n",
    "            while Q:\n",
    "                x = Q.pop(0)\n",
    "                y = Q.pop(-1)\n",
    "                nxt_Q.append('(' + x + ',' + y + ')')\n",
    "            Q = nxt_Q\n",
    "        return Q[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        arr=[str(i) for i in range(1,n+1)]\n",
    "        print(arr[0])\n",
    "      #  print\n",
    "        n=len(arr)\n",
    "       # arr=0\n",
    "        while n>1:\n",
    "            nex=[]\n",
    "            for i in range(n//2):\n",
    "                tmp=\"(\"+arr[i]+\",\"+arr[n-i-1]+\")\"\n",
    "                nex.append(tmp)\n",
    "            print(nex)\n",
    "            n=len(nex)\n",
    "            arr=nex[:]\n",
    "        return arr[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        Q = [str(x) for x in range(1, n + 1)]\n",
    "        while len(Q) > 1:\n",
    "            nxt_Q = []\n",
    "            while Q:\n",
    "                x = Q.pop(0)\n",
    "                y = Q.pop(-1)\n",
    "                nxt_Q.append('(' + x + ',' + y + ')')\n",
    "            Q = nxt_Q\n",
    "        return Q[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        stack=[]\n",
    "        left,right=1,n\n",
    "        for item in range(n//2):\n",
    "            stack.append((left,right))\n",
    "            left+=1\n",
    "            right-=1\n",
    "\n",
    "        while len(stack)!=1:\n",
    "            temp=[]\n",
    "            left,right=0,len(stack)-1\n",
    "            for item in range(len(stack)//2):\n",
    "                temp.append((stack[left],stack[right]))\n",
    "                left+=1\n",
    "                right-=1\n",
    "            stack=temp\n",
    "        ret=str(tuple(stack[0]))\n",
    "        real_ret=''\n",
    "        for i in ret:\n",
    "            if i!=' ':\n",
    "                real_ret+=i\n",
    "        return real_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        s = list(range(1,n + 1))\n",
    "        s = list(map(str,s))\n",
    "        \n",
    "        while len(s) > 1:\n",
    "            i,j = 0,len(s) - 1\n",
    "            t = []\n",
    "            while i < j:\n",
    "                t.append('('+ s[i] + ',' + s[j] +')')\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s = t\n",
    "        return s[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "      ans = [0] * n\n",
    "      def dfs(num, gap):\n",
    "        if num == 2:\n",
    "          ans[0::gap] = [\"1\", \"2\"]\n",
    "          return\n",
    "        \n",
    "        dfs(num // 2, gap * 2)\n",
    "        for i in range(gap, n, gap * 2):\n",
    "          ans[i] = str(1 + num - int(ans[i - gap]))\n",
    "      \n",
    "      dfs(n, 1)\n",
    "      while len(ans) > 1:\n",
    "        temp = []\n",
    "        for i in range(0, len(ans), 2):\n",
    "          temp.append(\"(\" + ans[i] + \",\" + ans[i+1] + \")\")\n",
    "        ans = temp\n",
    "      return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        l = tuple(range(1, n+1))\n",
    "        # return list(zip([1,2],[3,4]))\n",
    "        # l = tuple(zip(l[:n//2], l[:n//2-1:-1]))\n",
    "        # print(l)\n",
    "        # return\n",
    "        while n > 1:\n",
    "            l1 = tuple(zip(tuple(l[:n//2]), tuple(l[:n//2-1:-1])))\n",
    "            l, l1 = l1, []\n",
    "            n //= 2 \n",
    "        s = str(l[0])\n",
    "        res = \"\"\n",
    "        for char in s:\n",
    "            if char != \" \":\n",
    "                res += char\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "      ans = [0] * n\n",
    "      def dfs(num, gap):\n",
    "        if num == 2:\n",
    "          ans[0::gap] = [\"1\", \"2\"]\n",
    "          return\n",
    "        \n",
    "        dfs(num // 2, gap * 2)\n",
    "        for i in range(gap, n, gap * 2):\n",
    "          ans[i] = str(1 + num - int(ans[i - gap]))\n",
    "      \n",
    "      dfs(n, 1)\n",
    "      while len(ans) > 1:\n",
    "        temp = []\n",
    "        for i in range(0, len(ans), 2):\n",
    "          temp.append(\"(\" + ans[i] + \",\" + ans[i+1] + \")\")\n",
    "        ans = temp\n",
    "      return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        s = list(map(str,range(1,n + 1)))\n",
    "        while len(s) > 1:\n",
    "            i,j = 0,len(s) - 1\n",
    "            t = []\n",
    "            while i < j:\n",
    "                t.append('('+ s[i] + ',' + s[j] +')')\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            s = t\n",
    "        return s[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "\n",
    "        def dfs(data):\n",
    "            l, r = 0, len(data) - 1\n",
    "            n = len(data)\n",
    "            if n == 2:\n",
    "                return [f'({data[0]},{data[1]})']\n",
    "            \n",
    "            tmp = []\n",
    "            while l < r:\n",
    "                tmp.append(f'({data[l]},{data[r]})')\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return dfs(tmp)\n",
    "            \n",
    "        \n",
    "        return dfs([str(i) for i in range(1, n + 1)])[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "\n",
    "\n",
    "        def get_res(current_res):\n",
    "            n = len(current_res)\n",
    "            if n==2:\n",
    "                return \"(\"+current_res[0]+','+current_res[1]+')'\n",
    "            if n==1:\n",
    "                return current_res\n",
    "            \n",
    "            res = []\n",
    "            for i in range(len(current_res)//2):\n",
    "                res.append('(%s,%s)' % (current_res[i],current_res[-i-1]))\n",
    "            # print(res)\n",
    "            return get_res(res)\n",
    "        \n",
    "        res =  get_res([str(x+1) for x in range(n)])\n",
    "        # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        def f(a):\n",
    "            if len(a) == 1: return str(a[0])\n",
    "            b, n = [], len(a)\n",
    "            for x, y in zip(a[:n//2], a[n//2:][::-1]):\n",
    "                b.append(\"({},{})\".format(x, y))\n",
    "            return f(b)\n",
    "        return f(list(range(1, 1+n)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContestMatch(self, n: int) -> str:\n",
    "        team = [str(i) for i in range(1, n + 1)]\n",
    "        def dfs(n):\n",
    "            if n == 1:\n",
    "                return\n",
    "            for i in range(n // 2):\n",
    "                team[i] = '(' + team[i] + ',' + team[n - i - 1] + ')'\n",
    "            dfs(n // 2)\n",
    "        dfs(n)\n",
    "        return team[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
